package frist50;

import org.junit.jupiter.api.Test;

public class T0010 {
    public boolean isMatch(String s, String p) {
        return dp(s, p, s.length() - 1, p.length() - 1);


    }

    public boolean dp(String s, String p, int i, int j) {
        System.out.println(i + "  " + j);
        if (i == -1 && j == -1) return true;
        if (i == -1 && j % 2 == 1) {
            for (int k = j; k >-1; k-=2) {
                if(p.charAt(k)!='*')return false;
            }
            return true;
        }
        if (i == -1 && j == 1 && p.charAt(j) == '*') return true;
        if (i == -1 || j == -1) return false;
        if (p.charAt(j) != '*') {
            if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                return dp(s, p, i - 1, j - 1);
            } else {
                return false;
            }
        } else {
            if (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                return dp(s, p, i - 1, j) || dp(s, p, i, j - 2);
            } else {
                return dp(s, p, i, j - 2);
            }
        }
    }

    @Test
    public void test() {
        System.out.println(isMatch("aab", "c*a*b"));

    }
}
